package LC;

import java.util.*;

/**
 * https://leetcode.com/problems/course-schedule-ii/description/
 * There are a total of n courses you have to take, labeled from 0 to n - 1.
 * Some courses may have prerequisites, for example to take course 0 you
 * have to first take course 1, which is expressed as a pair: [0,1]
 * Given the total number of courses and a list of prerequisite pairs,
 * return the ordering of courses you should take to finish all courses.
 * There may be multiple correct orders, you just need to return one of them.
 * If it is impossible to finish all courses, return an empty array.
 * For example:
 * 2, [[1,0]]
 * There are a total of 2 courses to take. To take course 1 you should have finished course 0.
 * So the correct course order is [0,1]
 * 4, [[1,0],[2,0],[3,1],[3,2]]
 * There are a total of 4 courses to take.
 * To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be
 * taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
 * Note:
 * The input prerequisites is a graph represented by a list of edges, not adjacency matrices.
 * Read more about how a graph is represented.
 * You may assume that there are no duplicate edges in the input prerequisites.
 * click to show more hints.
 */
public class LC_210_CourseScheduleII_Queue {
    public static void main(String[] args) {
        int[][] prerequisites = {
                {1, 0},
                {2, 0},
                {3, 1},
                {3, 2}
        };
        int numCourses = 4;
        System.out.println(Arrays.toString(Solution.findOrder(numCourses, prerequisites)));
    }

    static class Solution {
        static int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] map = new int[numCourses];
            for (int[] p : prerequisites) {
                map[p[0]]++;
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < map.length; i++) {
                if (map[i] == 0) queue.add(i);
            }
            List<Integer> res = new ArrayList<>();
            int count = queue.size();
            while (!queue.isEmpty()) {
                int temp = queue.poll();
                res.add(temp);
                for (int[] prerequisite : prerequisites) {
                    if (temp == prerequisite[1]) {
                        int t = prerequisite[0];
                        map[t]--;
                        if (map[t] == 0) {
                            queue.add(t);
                            count++;
                        }
                    }
                }
            }
            if (count != numCourses) return new int[0];
            else {
                int[] a = new int[res.size()];
                for (int i = res.size() - 1; i >= 0; i--) {
                    a[i] = res.get(i);
                }
                return a;
            }
        }
    }
}